package com.company.heap;

import java.nio.BufferUnderflowException;

/**
 * Created by v on 16-12-7.
 */
public class LeftistHeap<E extends Comparable<E>> {
    private Node<E> root;
    private int size=0;

    private static class Node<E extends Comparable<E>>{
        private E element;
        private Node<E> left;
        private Node<E> right;
        private int npl;

        public Node(E element){
            this(element,null,null);
        }

        public Node(E element,Node<E> left,Node<E> right){
            this.element=element;
            this.left=left;
            this.right=right;
        }
    }

    public void merge(LeftistHeap<E> rhs){
        if(rhs==this){
            return;
        }

        merge1(root,rhs.root);
        size+=rhs.size;
        rhs.clear();
    }

    public void add(E e){
        root=merge1(new Node<E>(e),root);
        size++;
    }

    public E peek(){
        return root.element;
    }

    public E poll(){
        if(isEmpty()){
            throw new BufferUnderflowException();
        }

        E minElement=root.element;
        root=merge1(root.left,root.right);
        size--;
        return minElement;
    }

    public boolean isEmpty(){
        return root==null;
    }

    public void clear(){
        size=0;
        root=null;
    }

    //h1与h2为等位关系
    private Node<E> merge1(Node<E> h1,Node<E> h2){
        //h1与h2至多只有一个为null
        if(h1==null){
            return h2;
        }
        if(h2==null){
            return h1;
        }

        if(h1.element.compareTo(h2.element)<0){
            return merge2(h1,h2);
        }else {
            return merge2(h2,h1);
        }
    }

    //h1为小的结点,h2为大的结点
    private Node<E> merge2(Node<E> h1,Node<E> h2){
        if(h1.left==null){
            h1.left=h2;
        }else {
            h1.right=merge1(h1.right,h2);
            if(h1.left.npl<h1.right.npl)
                swapChildren(h1);

            h1.npl=h1.right.npl+1;
        }
        return h1;
    }

    private void swapChildren(Node<E> t){
        Node<E> temp=t.left;
        t.left=t.right;
        t.right=temp;
    }

    public int getSize() {
        return size;
    }
}